#include <stdio.h>
#include <stdlib.h>

typedef struct List{
    int *data;
    int length;//长度
    int num;//个数
} List;

List *initList(int length) 
{
    List *L = (List *)malloc(sizeof(List));
    L->length = length;
    L->data = (int *)malloc(sizeof(int) * length);
    L->num = 1; //带哨兵的 普通的是初始化为0 0号单元初始化为key
    return L;
}

//假设线性表中都是正数

void listAdd(List *list, int data) 
{
    list->data[(list->num++)] = data;
    //list->num = (list->num) + 1;
}

int search(List *L, int key)
{
    for (int i = 0; i < L->num; i++) {
        if (L->data[i] == key) {
            return i; //返回下标
        }
    }
    return -1;
}

//少一个判断带哨兵不需要判断是否越界
int search_1(List *L, int key) 
{
    int i;
    L->data[0] = key;
    for (i = L->length-1; L->data[i] != key; i--);
    return i;
}

void printList(List *L)
{
    for (int i = 1; i < L->num; i++) {
        printf("%d ->", L->data[i]);
    }
    printf("NULL\n");
}

int main(void)
{
    List *L = initList(5);  //第一个元素是哨兵
    listAdd(L, 1);
    listAdd(L, 2);
    listAdd(L, 3);
    listAdd(L, 4);
    listAdd(L, 5); //这里越界了
    printList(L);
    int test = search_1(L, 4);
    printf("%d\n", test);
    return 0;
}